Technical Field
The present invention relates to program optimization, and more particularly to systems and methods for using traces to inductively infer substitute program elements to reduce computational complexity.
Description of the Related Art
Program optimization can be considered a process to transform a program by applying prepared rules. For example, in peephole optimization, rules such as: “x*=2→x<<=1”, can be prepared, and an entire program can be scanned to apply the rules where applicable. However, to perform higher-level optimizations, the combination of rule applications causes the computation to explode. The problem is not only in the large number of rules, but also it is necessary to apply multiple rules. This is why searching is necessary, but the searching results in combinatorial explosion. Heuristics do not work well, because each rule by itself does not speed up the program, so it is difficult to decide on a search direction in the search space.